from typing import List
from typing import Tuple

from sortedcontainers import SortedList


class BlackBox:

    def __init__(self, n: int, m: int):
        self.n, self.m = n, m  # m为横边长，n为竖边长
        self.size = m * 2 + n * 2  # 计算小孔总数
        self.corner = 0, m, m + n, 2 * m + n  # 计算拐角小孔的下标

        # ---------- 统计所有光路 ----------
        # 光路列表：path[i] = [当前结点,当前结点到达当前结点右侧结点的方向]
        # 【定义名词】单向光路：原路返回的光路（即包含拐角小孔）
        # 【定义名词】循环光路：不原路返回的光路（即不包含拐角小孔）
        # 时间复杂度：O(N+M)

        self.path = []

        visited = set()

        # 优先遍历拐角处小孔所在光路：因为包含拐角处小孔的循环是原路返回的，而遍历时考虑了当前小孔是否被遍历过
        # 如果从非拐角处的小孔，开始遍历包含拐角处小孔的循环，不能完整遍历该循环，只能循环其中一侧（会停在拐角处的小孔上）
        for k in self.corner:
            if k in visited:
                continue

            # 当前小孔为左上或右下的情况
            if k == self.corner[0] or k == self.corner[2]:
                self.path.append(self._single_go_back(self._search(k, -1, visited)))  # 添加沿着唯一方向-1寻找光路（包含返回路径）

            # 当前小孔为右上或左下的情况
            else:  # k == self.corner[1] or k == self.corner[3]
                self.path.append(self._single_go_back(self._search(k, 1, visited)))  # 添加沿着唯一方向+1寻找光路（包含返回路径）

        # 随后遍历非拐角处小孔所在光路
        for k in range(self.size):
            if k in visited:
                continue
            self.path.append(self._search(k, 1, visited))  # 添加沿着方向+1的光路
            self.path.append(self._circle_go_back(self.path[-1]))  # 添加沿着方向-1的光路（方向+1的光路的逆向光路）

        # print("光路列表:", self.path)

        # ---------- 构造统计小孔及方向对应光路的哈希表 ----------
        # 时间复杂度：O(N+M)

        self.index = {}

        for i, path in enumerate(self.path):
            for j, (k, d) in enumerate(path):
                self.index[(k, d)] = (i, j)

        # print("小孔对应光路:", self.index)

        # ---------- 初始化光路开孔情况列表 ----------
        # 时间复杂度：O(N+M)

        self.opening = [SortedList() for _ in range(len(self.path))]

        # print("光路开孔情况表:", self.opening)

    def open(self, k: int, d: int) -> int:
        """打开小孔k并射入方向为d的光线，返回光线射出的小孔"""

        # ---------- 更新光路开孔情况列表 ----------
        # 时间复杂度：O(log(N+M))

        # 当前小孔为拐角小孔时：只需要标记一个光线方向即可
        if k in self.corner:
            i, j = self.index[(k, d)]
            if j not in self.opening[i]:
                self.opening[i].add(j)

        # 当前小孔为边上小孔时：需要标记两个光线方向
        else:
            i1, j1 = self.index[(k, 1)]
            i2, j2 = self.index[(k, -1)]
            if j1 not in self.opening[i1]:
                self.opening[i1].add(j1)
            if j2 not in self.opening[i2]:
                self.opening[i2].add(j2)

        # ---------- 二分查找计算光线射出的小孔 ----------
        # 寻找当前光线所在光路上，当前小孔和方向后最近的已被标记的小孔
        i, j = self.index[(k, d)]

        # 寻找严格大于j的第1个被标记的小孔
        res = self.opening[i].bisect_right(j)  # 下一个小孔在被标记的小孔列表的下标
        if res == len(self.opening[i]):
            res = 0
        res = self.opening[i][res]  # 下一个小孔在光路上的下标

        # print("开孔:", [k, d], "->", i, ":", self.opening[i], "->", j, "->", res, "=", self.path[i][res])

        return self.path[i][res][0]

    def close(self, k: int) -> None:
        """关闭小孔k"""

        # ---------- 更新光路开孔情况列表 ----------
        # 时间复杂度：O(log(N+M))

        # 当前小孔为拐角小孔时：只需要标记一个光线方向即可
        if k == self.corner[0] or k == self.corner[2]:
            i, j = self.index[(k, -1)]
            if j in self.opening[i]:
                self.opening[i].remove(j)
        elif k == self.corner[1] or k == self.corner[3]:
            i, j = self.index[(k, 1)]
            if j in self.opening[i]:
                self.opening[i].remove(j)

        # 当前小孔为边上小孔时：需要标记两个光线方向
        else:
            i1, j1 = self.index[(k, 1)]
            i2, j2 = self.index[(k, -1)]
            if j1 in self.opening[i1]:
                self.opening[i1].remove(j1)
            if j2 in self.opening[i2]:
                self.opening[i2].remove(j2)

    @staticmethod
    def _single_go_back(path: List[Tuple[int, int]]):
        """将单向光路的返回路径添加到光路中"""
        if len(path) > 2:
            for j in range(len(path) - 2, 0, -1):
                path.append((path[j][0], (-1) * path[j][1]))
        return path

    @staticmethod
    def _circle_go_back(path: List[Tuple[int, int]]):
        """生成循环光路的反向光路"""
        return [(k, -d) for k, d in path[::-1]]

    def _search(self, k: int, d: int, visited: set):
        """以方向d从小孔k出发寻找光路，直到回到小孔k或到达拐角折回"""
        path = []
        while k not in visited:
            d = self._reflect(k, d)  # 计算反射方向
            path.append((k, d))
            visited.add(k)
            k = self._shoot(k, d)  # 计算下一个到达的小孔
        return path

    def _reflect(self, k: int, d: int):
        """计算以方向d入射到小孔i的反射方向"""
        if k in self.corner:
            return d
        else:
            return (-1) * d

    def _shoot(self, k: int, d: int):
        """计算以方向d从小孔i出发到达的小孔"""

        # 当前位置：左上角  方向：右下
        if k == self.corner[0]:
            if self.m > self.n:  # 横边长 > 竖边长
                return self.corner[3] - self.n
            elif self.m < self.n:  # 横边长 < 竖边长
                return self.corner[1] + self.m
            else:  # 横边长 == 竖边长
                return self.corner[2]

        # 当前位置：上边
        elif self.corner[0] < k < self.corner[1]:
            if d == 1:  # 方向：左下
                if k <= self.n:  # 横边(当前位置左侧)长 <= 竖边长
                    return self.size - k
                else:  # 横边(当前位置左侧)长 > 竖边长
                    return self.corner[3] - (k - self.n)
            else:  # 方向：右下
                if (self.corner[1] - k) < self.n:  # 横边(当前位置右侧)长 <= 竖边长
                    return self.corner[1] + (self.corner[1] - k)
                else:  # 横边(当前位置右侧)长 > 竖边长
                    return self.corner[2] + ((self.corner[1] - k) - self.n)

        # 当前位置：右上角  方向：左下
        elif k == self.corner[1]:
            if self.m > self.n:  # 横边长 > 竖边长
                return self.corner[2] + self.n
            elif self.m < self.n:  # 横边长 < 竖边长
                return self.size - self.m
            else:  # 横边长 == 竖边长
                return self.corner[3]

        # 当前位置：右边
        elif self.corner[1] < k < self.corner[2]:
            if d == 1:  # 方向：左下
                if (self.corner[2] - k) <= self.m:  # 竖边(当前位置下方)长 <= 横边长
                    return self.corner[2] + (self.corner[2] - k)
                else:  # 竖边(当前位置下方)长 > 横边长
                    return self.corner[3] + ((self.corner[2] - k) - self.m)
            else:  # 方向：左上
                if (k - self.corner[1]) <= self.m:  # 竖边(当前位置上方)长 <= 横边长
                    return self.corner[1] - (k - self.corner[1])
                else:  # 竖边(当前位置上方)长 > 横边长
                    return self.size - ((k - self.corner[1]) - self.m)

        # 当前位置：右下角  方向：左上
        elif k == self.corner[2]:
            if self.m > self.n:  # 横边长 > 竖边长
                return self.corner[1] - self.n
            elif self.m < self.n:  # 横边长 < 竖边长
                return self.corner[3] + self.m
            else:  # 横边长 == 竖边长
                return self.corner[0]

        # 当前位置：下边
        elif self.corner[2] < k < self.corner[3]:
            if d == 1:  # 方向：右上
                if (k - self.corner[2]) <= self.n:  # 横边(当前位置右侧)长 <= 竖边长
                    return self.corner[2] - (k - self.corner[2])
                else:  # 横边(当前位置右侧)长 > 竖边长
                    return self.corner[1] - ((k - self.corner[2]) - self.n)
            else:  # 方向：左上
                if (self.corner[3] - k) <= self.n:  # 横边(当前位置左侧)长 <= 竖边长
                    return self.corner[3] + (self.corner[3] - k)
                else:  # 横边(当前位置左侧)长 > 竖边长
                    return self.corner[0] + ((self.corner[3] - k) - self.n)

        # 当前位置：左下角  # 方向：右上
        elif k == self.corner[3]:
            if self.m > self.n:  # 横边长 > 竖边长
                return self.corner[0] + self.n
            elif self.m < self.n:  # 横边长 < 竖边长
                return self.corner[2] - self.m
            else:  # 横边长 == 竖边长
                return self.corner[1]

        # 当前位置：左边
        else:
            if d == 1:  # 方向：右上
                if (self.size - k) <= self.m:  # 竖边(当前位置上方)长 <= 横边长
                    return self.corner[0] + (self.size - k)
                else:  # 竖边(当前位置上方)长 > 横边长
                    return self.corner[1] + ((self.size - k) - self.m)
            else:  # 方向：右下
                if (k - self.corner[3]) <= self.m:  # 竖边(当前位置下方)长 <= 横边长
                    return self.corner[3] - (k - self.corner[3])
                else:  # 竖边(当前位置下方)长 > 横边长
                    return self.corner[2] - ((k - self.corner[3]) - self.m)


if __name__ == "__main__":
    obj = BlackBox(2, 3)
    print(obj.open(6, -1))  # 6
    print(obj.open(4, -1))  # 4
    print(obj.open(0, -1))  # 6
    obj.close(6)
    print(obj.open(0, -1))  # 4
    print()

    obj = BlackBox(3, 3)
    print(obj.open(1, -1))  # 1
    print(obj.open(5, 1))  # 1
    print(obj.open(11, -1))  # 5
    print(obj.open(11, 1))  # 1
    obj.close(1)
    print(obj.open(11, 1))  # 5
    obj.close(5)
    print(obj.open(11, -1))  # 11
    print()

    # 测试用例4/39
    obj = BlackBox(1, 6)
    print(obj.open(7, -1))  # 7
    print(obj.open(7, -1))  # 7
    obj.close(7)
    print(obj.open(3, 1))  # 3
    print()
    # ......
